package 单周赛.history;

import util.ListNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 *
 */
public class 第321场单周赛 {

    public static void main(String[] args) {

        System.out.println(pivotInteger(8));

        System.out.println(appendCharacters("z", "abcde"));

        ListNode node5 = new ListNode(5);
        ListNode node2 = new ListNode(2);
        ListNode node13 = new ListNode(13);
        ListNode node3 = new ListNode(3);
        ListNode node8 = new ListNode(8);
        node5.next = node2;
        node2.next = node13;
        node13.next = node3;
        node3.next = node8;
        removeNodes(node5);

    }

    public static int pivotInteger(int n) {
        int[] prefixSum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + i;
        }
        for (int i = 1; i <= n; i++) {
            if (prefixSum[i] > prefixSum[n] - prefixSum[i - 1]) {
                return -1;
            }
            if (prefixSum[i] == prefixSum[n] - prefixSum[i - 1]) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 在 s 中尽可能按顺序匹配 t 相同字符的最多个数
     *
     * @param s
     * @param t
     * @return
     */
    public static int appendCharacters(String s, String t) {
        int sIdx = 0, tIdx = 0;
        while (sIdx < s.length() && tIdx < t.length()) {
            while (sIdx < s.length() && s.charAt(sIdx) != t.charAt(tIdx)) {
                sIdx++;
            }
            if (sIdx == s.length()) break;

            tIdx++;
            sIdx++;
        }
        return t.length() - tIdx;
    }

    /**
     * 单调栈模拟
     *
     * @param head
     * @return
     */
    public static ListNode removeNodes(ListNode head) {
        Deque<Integer> stack = new ArrayDeque<>();
        while (head != null) {
            while (!stack.isEmpty() && stack.peekFirst() < head.val) {
                stack.pollFirst();
            }
            stack.addFirst(head.val);
            head = head.next;
        }

        ListNode realHead = new ListNode(stack.pollLast());

        ListNode curNode = realHead;
        while (!stack.isEmpty()) {
            ListNode nextNode = new ListNode(stack.pollLast());
            curNode.next = nextNode;
            curNode = curNode.next;
        }
        return realHead;
    }

}
